package com.hejjon;

/**
 * [9]
 * [1,9,9,9,9,9,9,9,9,9]
 * Created by caoshi at 6:12 2021-06-27
 */

public class AddTwoNumbers {

    public static void main(String[] args) {
        ListNode l1 = createByArray(new int[]{2, 4, 3});
        ListNode l2 = createByArray(new int[]{5, 6, 4});

        ListNode listNode = new AddTwoNumbers().addTwoNumbers(l1, l2);
        printListNode(listNode);

    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode resNode = new ListNode(0);
        ListNode p = l1, q = l2;
        ListNode curr = resNode;
        int carry = 0, sum = 0;
        while (p != null || q != null) {
            sum = carry + (p == null ? 0 : p.val) + (q == null ? 0 : q.val);
            carry = sum / 10;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            if (p != null) {
                p = p.next;
            }
            if (q != null) {
                q = q.next;
            }
            if (carry > 0) {
                curr.next = new ListNode(carry);
            }

        }

        // 返回resNode.next 是为了去掉首位的0
        return resNode.next;
    }


    /**
     * [4, 2, 3, 5, 2, 3]
     *
     * @param arr
     */
    private static ListNode createByArray(int[] arr) {
    // 初始化头节点, 节点的数据是数组的首位元素
    ListNode head = new ListNode(arr[0]);
    // 初始化尾节点, 初始指向头节点
    ListNode end = head;
    for (int i = 1; i < arr.length; i++) {
        ListNode node = new ListNode();
        node.val = arr[i];
        end.next = node;
        end = node;
    }
        return head;
    }


    private static void printListNode(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
    }


}

/**
 * 定义单链表数据结构
 */
class ListNode {

    int val;        // 当前节点数据
    ListNode next;  // 当前节点的下一个节点指向

    public ListNode() {
    }

    public ListNode(int val) {
        this.val = val;
    }

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
